using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace SchedulerSupreme
{
	public class Schedule
	{
        static int WEEKSIZE = 5;

        public int Departments{get {return departments;}}
        public int Types { get { return types; } }
        public int Days { get { return days; } }
        public int Slots { get { return slots; } }
        public int Weeks { get { return weeks; } }
        public int Size { get { return schedule.Length; } }
        public double Hours { get { return sum() / 2; } }
        public double[] WeightIndex { get { return weightIndex; } }

        private bool weighted;
        private double[] weightIndex;
        private int departments, types, days, slots, weeks;
		private int[] schedule;

        public double Demanddeviation
        {
            get { return costDemandDifference(); }
        }
        public double Weekdeviation
        {
            get {return costWeekDeviation(); }
        }
        public double Yeardeviation
        {
            get { return costYearDeviation(); }
        }
        public double Capcost
        {
            get { return costEmployeeCap();}
        }
        
        #region Datastructure

		public Schedule (int departments, int types, int days, int slots)
		{
			this.departments = departments;
			this.types = types;
			this.days = days;
			this.slots = slots;

            this.weeks = days / WEEKSIZE;
			
			schedule = new int[departments * types * days * slots];
			for (int i = 0; i < schedule.Length; i++) {
				schedule[i] = 0;
			}
		}

        public void addWeightIndex(double[] weightIndex)
        {
            if (weightIndex.Length != departments)
                throw new IndexOutOfRangeException("Weight index not correlating to number of departments.");

            this.weighted = true;
            double weightRatio = weightIndex.Sum()/weightIndex.Length;

            for (int i = 0; i < weightIndex.Length; i++)
                weightIndex[i] = weightIndex[i] / weightRatio;

            this.weightIndex = weightIndex;
            
        }
		
		// Macro to find the slot to read or write; makes changing stuff easier
		private int computeIndex(int department, int type, int day, int slot)
		{
            Debug.Assert(department < departments && type < types && day < days && slot < slots);

			// TODO: measure speed against 4-dimensional array
			return department * types * days * slots
					+ day * types * slots
					+ type * slots
					+ slot;
		}
		
		public void populateRandomly()
		{
            // TODO: Should populate the schedule randomly
		}


		public Schedule Clone()
		{
			Schedule clone = new Schedule(departments, types, days, slots);
			return Clone(clone);
		}

        public Schedule Clone(Schedule clone)
        {

            for (int i = 0; i < schedule.Length; i++)
            {
                clone.schedule[i] = schedule[i];
            }

            if(weighted)
                clone.addWeightIndex(weightIndex);

            return clone;
        }

        public int getAssignment(int department, int type, int day, int slot)
		{
			int index = computeIndex(department, type, day, slot);
			return schedule[index];
		}
		
		public void assign(int department, int type, int day, int slot, int assignment)
		{
			int index = computeIndex(department, type, day, slot);
			schedule[index] = assignment;
		}

        public void add(int department, int type, int day, int slot, int assignment)
        {
            int index = computeIndex(department, type, day, slot);
            schedule[index] += assignment;
        }

        private double getWeek(int department, int type, int week)
        {
            int weekStart = computeIndex(department, type, week * WEEKSIZE, 0);
            int weekLength = WEEKSIZE * slots;
            int currentWeek = schedule.Skip(weekStart).Take(weekLength).Sum();
            
            return currentWeek;
        }

        public int getDepTypeSum(int department, int type)
        {
            if (department < this.departments && type < this.types)
            {
                int result = 0;
                for (int d = 0; d < days; d++)
                {
                    for (int s = 0; s < slots; s++)
                    {
                        result += getAssignment(department, type, d, s);
                    }
                }
            return result;
            }
            throw new ArgumentOutOfRangeException("No such department or type");           
        }

        private int getTypeDaySlotSum(int type, int day, int slot)
        {
            if (type < this.types && day < this.days && slot < this.Slots)
            {
                int result = 0;
                for (int d = 0; d < departments; d++)
                {
                    result += getAssignment(d, type, day, slot);
                };
                return result;
            }
            throw new ArgumentOutOfRangeException("No such department or type");
        }

        public void addDepartments(int noDeps)
        {
            if (noDeps >= 0)
            {
                this.departments = this.Departments + noDeps;
                int[] Added_schedule = new int[departments * types * days * slots];
                for (int i = 0; i < schedule.Length; i++)
                {
                    Added_schedule[i] = schedule[i];
                }

                this.schedule = Added_schedule;
            }
        }

        #endregion

        public List<Shift> Shifts(){
        List<Shift> shifts = new List<Shift>();
        int[] dayResidual = new int[Slots];
        int pointer = 0;
        int Nextpointer = 0;
        int sp = 0;
        int slots = 0;
        int gapsJumped = 0;
        int maxGap = 2;
        int minSize = 4;

        for (int department = 0; department < Departments; department++)
            for (int type = 0; type < Types; type++)
                for (int day = 0; day < Days; day++)
                {
                    dayResidual = new int[Slots];
                    for (int slot = 0; slot < Slots; slot++)
                    {
                        pointer = computeIndex(department, type, day, slot);
                        while (schedule[pointer]+dayResidual[slot] > 0)
                        {
                            sp = pointer;
                            slots = 1;
                            dayResidual[slot] -= 1;
                            int introHour = 0;
                            for (int shiftSlot = slot+1; shiftSlot < Slots; shiftSlot++)
                            {
                                Nextpointer = computeIndex(department, type, day, shiftSlot);
                                //The next slot is not empty and there are remaining slots in the day
                                if (schedule[Nextpointer] + dayResidual[shiftSlot] > 0)
                                {
                                    slots += 1;
                                    dayResidual[shiftSlot] -= 1;
                                }
                                //If an empty slot is encoutered and we are about minSize...
                                else if (slots >= minSize) 
                                    { 
                                    pointer = computeIndex(department, type, day, slot); 
                                    break; 
                                    }
                                //If an empty slot is encourered and we have jumped further than good, the shift is finished.
                                else if (slots < minSize && gapsJumped > maxGap)
                                {                                    
                                    gapsJumped = 0;
                                    if (slots == 1 && slot > computeIndex(department, type, day, 0)) { introHour = 1; }
                                    slots = 4;
                                    pointer = computeIndex(department, type, day, slot);
                                    break;
                                }
                                //We notice the gap and carry on.
                                else
                                {
                                    gapsJumped+=1;
                                }
                            }
                            shifts.Add(new Shift(day,type,slot-introHour,slots));
                        }
                    }
                }
        return shifts;
        }

        #region Cost functions

        public double sum()
        {
            return schedule.Sum();
        }

        public double Cost()
        {
            try
            {
                return costDemandDifference()
                    + costYearDeviation()
                    + costWeekDeviation()
                    + 0.25*costEmployeeCap();
            }
            catch (System.NullReferenceException e)
            {
                Console.WriteLine("Demand not set! Please check input. {0}", e.Message);
                Console.ReadKey();
                Environment.Exit(-1);
                return 0;
            }
        }


        #region DemandDifference

        private double costDemandDifference()
        {
            return Math.Abs(Program.Demand.schedule.Sum() - schedule.Sum());
        }

        #endregion

        #region YearDeviation

        private double costYearDeviationType(int type)
		{
            double[] sums = new double[departments];
            int step = schedule.Length / departments;
            int stepType = type * days * slots;
            int stepLength = days * slots;


            for (int i = 0; i < departments; i++)
            {
                sums[i] = schedule.Skip(i * step+stepType).Take(stepLength).Sum();
                if (weighted)
                    sums[i] = sums[i] * weightIndex[i];
            }



            double mean = sums.Average();
            double sumDiff = sums.Select(x => (x - mean) * (x - mean)).Sum();
            return Math.Sqrt(sumDiff / sums.Length);
		}

        private double costYearDeviation()
        {
            double sum = 0;
            for (int i = 0; i < types; i++)
                sum += costYearDeviationType(i);
            return sum;
        }

        #endregion

        #region WeekDeviation

        private double costWeekDeviationTypeWeek(int type, int week)
        {
            double[] sums = new double[departments];

            for (int i = 0; i < departments; i++)
            {
                sums[i] = getWeek(i, type, week);
                if (weighted)
                    sums[i] = sums[i] * weightIndex[i];
            }


            double mean = sums.Average();
            double sumDiff = sums.Select(x => (x - mean) * (x - mean)).Sum();
            return Math.Sqrt(sumDiff / sums.Length);
        }

        private double costWeekDeviation()
        {
            double sum = 0;
            for (int i = 0; i < types; i++)
                for (int j = 0; j < weeks; j++)
                    sum += costWeekDeviationTypeWeek(i, j);
            return sum;
        }

        #endregion

        #region employeeCap

        private double costEmployeeCap()
        {
            if (weighted)
                return CostCapWeighted();
            else
                return costCap();
        }
        private double costCap()
        {
            int aboveCap=0;
            foreach(int noEmployess in schedule)
                aboveCap += Math.Max(0, noEmployess - Program.Cap);
            return aboveCap;
        }

        private double CostCapWeighted()
        {
            double aboveCap = 0;
            int departmentLength = schedule.Length / departments;
            int tempDepLength = departmentLength;
            int currentDep = 0;
            foreach (double noEmployess in schedule)
            {
                if (tempDepLength == 0)
                {
                    currentDep++;
                    tempDepLength = departmentLength;
                }
                aboveCap += Math.Max(0.0, noEmployess - Program.Cap * weightIndex[currentDep]);
                tempDepLength--;
            }
            return aboveCap;
        }


        #endregion

        #endregion

        #region Neighbors

        //Legacy
        public Schedule[] Neighborhood(){
            
            //Find the lowest scoring department for each type:
            int[] leastDep=new int[types];
            for(int type=0;type<types;type++)
            {
                int lowTracker = int.MaxValue;
                for (int dep = 0; dep < departments; dep++)
                {
                    int sum;
                    if (weighted)
                        sum = getDepTypeSum(dep, type) * (int)weightIndex[dep];
                    else
                        sum = getDepTypeSum(dep, type);
                    if (sum < lowTracker)
                    {
                        leastDep[type] = dep;
                        lowTracker = sum;
                    }
                }
            }

            //Create an assignment with all shifts in one day and type moved to lowest scoring departement
            //And add it to the neighborhood.
            Schedule[] neighborhood = new Schedule[types*days];
            for (int type = 0; type < types; type++)
            {
                for(int day=0;day<days;day++)
                {
                    int neighbor_index = (type * days) + day;
                    neighborhood[neighbor_index] = this.Clone();
                        for (int slot = 0; slot < slots; slot++)
                        {
                            int sum = getTypeDaySlotSum(type, day, slot);
                            for(int dep=0;dep<departments;dep++){
                                if (dep == leastDep[type])
                                {
                                    neighborhood[neighbor_index].assign(dep, type, day, slot, sum);
                                }
                                else
                                {
                                    neighborhood[neighbor_index].assign(dep, type, day, slot, 0);
                                }
                               
                            } 
                        }
                }     
            }

            return neighborhood;


        }

        private Schedule Neighbor_old(int day, int type)
        {
            //Find the lowest scoring department for each type:
            int[] leastDep = new int[types];
                int lowTracker = int.MaxValue;
                for (int dep = 0; dep < departments; dep++)
                {
                    int sum;
                    if(weighted)
                        sum = (int) (getDepTypeSum(dep, type) * weightIndex[dep]);
                    else
                        sum = getDepTypeSum(dep, type);
                    if (sum < lowTracker)
                    {
                        leastDep[type] = dep;
                        lowTracker = sum;
                    }
                }

            //Create an assignment with all shifts in one day and type moved to lowest scoring departement
            //And add it to the neighborhood.
            Schedule neighbor = this.Clone();
                    int neighbor_index = (type * days) + day;
                    for (int slot = 0; slot < slots; slot++)
                    {
                        int sum = getTypeDaySlotSum(type, day, slot);
                        for (int dep = 0; dep < departments; dep++)
                        {
                            if (dep == leastDep[type])
                            {
                                neighbor.assign(dep, type, day, slot, sum);
                            }
                            else
                            {
                                neighbor.assign(dep, type, day, slot, 0);
                            }

                        }
                    }

            return neighbor;

        }

        private Schedule Neighbor_new(int day, int type)
        {
            //Find the lowest scoring department for each type:
            int[] depOrder = new int[departments];
            for(int dep = 0;dep<departments;dep++)
                depOrder[dep] = dep; 

            // calculate sums once and for all!
            int[] depTypeSum = new int[departments];
            for (int i = 0; i < depOrder.Length; i++)
                depTypeSum[i] = getDepTypeSum(depOrder[i], type);

            Array.Sort(depOrder, (x, y) => depTypeSum[x].CompareTo(depTypeSum[y]));
            
            //Create an assignment with all shifts in one day and type moved to lowest scoring departement
            //And add it to the neighborhood.
            Schedule neighbor = this.Clone();
            
            for (int slot = 0; slot < slots; slot++)
            {
                int sum = getTypeDaySlotSum(type, day, slot);
                if (sum > Program.Cap)
                {
                    int rounded = (sum % 2);
                    neighbor.assign(depOrder[0], type, day, slot, sum/2+rounded);
                    neighbor.assign(depOrder[1],type, day, slot, sum/2);
                }
                else
                {
                    neighbor.assign(depOrder[0], type, day, slot, sum);
                }

                for (int dep = 0; dep < departments; dep++)
                {
                    if (dep != depOrder[0])
                    {
                        if (sum > Program.Cap)
                        {
                            if (dep != depOrder[1])
                                neighbor.assign(dep, type, day, slot, 0);
                        }
                        else
                        {
                            neighbor.assign(dep, type, day, slot, 0);
                        }
                    }

                }
            }

            return neighbor;

        }

        private Schedule Neighbor_newRich(int day, int type)
        {
            int[] depOrder = new int[departments];
            for (int dep = 0; dep < departments; dep++)
                depOrder[dep] = dep; 

            // calculate sums once and for all!
            int[] depTypeSum = new int[departments];
            for (int dep = 0; dep < depOrder.Length; dep++)
                depTypeSum[dep] = (int) (getDepTypeSum(depOrder[dep], type) * weightIndex[dep]); 

            Array.Sort(depOrder, (x, y) => depTypeSum[x].CompareTo(depTypeSum[y]));

            //Create an assignment with all shifts in one day and type moved to lowest scoring departement
            //And add it to the neighborhood.
            Schedule neighbor = this.Clone();

            for (int slot = 0; slot < slots; slot++)
            {
                int rich = getAssignment(depOrder[departments - 1], type, day, slot);
                if (rich > Program.Cap)
                {
                    int rounded = (rich % 2);
                    neighbor.add(depOrder[0], type, day, slot, (rich / 2) + rounded);
                    neighbor.add(depOrder[1], type, day, slot, rich / 2);
                }
                else
                {
                    neighbor.add(depOrder[0], type, day, slot, rich);
                }

                neighbor.assign(depOrder[departments - 1], type, day, slot, 0);                
            }

            return neighbor;

        }

        private Schedule Neighbor_newRichRandom(int day, int type)
        {
            Random R = new Random();
            int from = R.Next(0, departments - 1);
            int to = 0;
            int to2 = 0;
            Boolean other = false;
            while (!other)
            {
                to = R.Next(0, departments - 1);
                if (from != to) other = true;
            }
            other = false;
            while (!other)
            {
                to2 = R.Next(0, departments - 1);
                if (from != to2 && to !=to2) other = true;
            }
            //Create an assignment with all shifts in one day and type moved to lowest scoring departement
            //And add it to the neighborhood.
            Schedule neighbor = this.Clone();


            for (int slot = 0; slot < slots; slot++)
            {
                int rich = getAssignment(from, type, day, slot);
                if (rich > Program.Cap)
                {
                    int rounded = (rich % 2);
                    neighbor.add(to, type, day, slot, (rich / 2) + rounded);
                    neighbor.add(to2, type, day, slot, rich / 2);
                }
                else
                {
                    neighbor.add(to, type, day, slot, rich);
                }

                neighbor.assign(from, type, day, slot, 0);
            }

            return neighbor;

        }

        public Schedule Neighbor(int day, int type)
        {
            return Neighbor_newRichRandom(day,type);
        }
            
        public String toString()
        {
            String output = "";

            // print headline
            output += "Department/Type, ";
            for (int day = 0; day < days; day++)
            {
                output += "Day " + (day + 1).ToString() + ", ";
            }
            output += Environment.NewLine;

            // print content
            for (int department = 0; department < departments; department++)
            {
                output += "Department " + (department + 1).ToString() + "," + Environment.NewLine;
                for (int type = 0; type < types; type++)
                {
                    output += "Type " + (type + 1).ToString() + Environment.NewLine;
                    for (int slot = 0; slot < slots; slot++)
                    {
                        output += ", ";
                        for (int day = 0; day < days; day++)
                        {
                            output += getAssignment(department, type, day, slot).ToString() + ", ";
                        }
                        output += Environment.NewLine;
                    }
                }
            }

            return output;
        }

        #endregion

    }
}